package aufgabe5;

import java.util.ArrayList;
import java.util.List;

import aufgabe4.EnhancedSuffixArray;

public class SuffixTree {
	
	public SuffixTree(String s) {
		createFromSuffixArray(s);
	}

	private void createFromSuffixArray(String s) {
		EnhancedSuffixArray esa = new EnhancedSuffixArray(s);
		List<Leaf> leafs = new ArrayList<Leaf>();
		
		TreeNode v = new TreeNode();
		TreeNode vx;
		
		v.d       = 0;
		vx        = new Leaf(esa.SUF[0]);
		vx.d      = esa.SSUF[0].length();
		vx.parentLabel = esa.SSUF[0];
		vx.parent = v;		
		v         = vx;
		
		leafs.add((Leaf) vx);
		
		for (int i = 1; i < esa.SUF.length; i++) {
			vx = new Leaf(esa.SUF[i]);
			vx.d = esa.SSUF[i].length();
			vx.parentLabel = esa.SSUF[i];
			
			leafs.add((Leaf) vx);
			
			while (v.parent != null && v.parent.d >= esa.LCP[i]) {
				v = v.parent;
			}
			
			if (v.d == esa.LCP[i]) {
				vx.parent      = v;
				vx.parentLabel = esa.s.substring(esa.SUF[i]+esa.LCP[i]);
			}
			else {				
				TreeNode wx = TreeNode.splitedge(v.parent, v, (esa.LCP[i] - v.parent.d), i, esa);
				
				vx.parent = wx;
				vx.parentLabel = esa.s.substring(esa.SUF[i]+esa.LCP[i]);
			}
			
			v = vx;
		}
		
		String out = "digraph suffix_tree {\n";
		
		for (Leaf l: leafs) {
			out += printPath(l);
		}
		
		out += "}";
		
		System.out.print(out);
	}
	
	public static String printPath(TreeNode n) {		
		n.printed = true;
		
		if (n.parent.parent == null) {
			return "\troot -> "+n.parentLabel+" [label="+n.parentLabel+"];\n";
		}
		else {
			String result = (n.parent.printed) ? "" : printPath(n.parent);
			
			return result +"\t"+ getNodeLabel(n.parent)+" -> "+getNodeLabel(n)+" [label="+n.parentLabel+"];\n";
		}
	}
	
	public static String getNodeLabel(TreeNode n) {
		return (n.parent == null) ? "" : getNodeLabel(n.parent)+n.parentLabel;
	}
	
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		SuffixTree s = new SuffixTree("ababX");
//		SuffixTree s = new SuffixTree("ggctagcga");
		
		SuffixTree s = new SuffixTree(args[0]);
	}

	
	private static class TreeNode {
		public TreeNode parent = null;
		public int d;
		public String parentLabel;
		public boolean printed = false;
		
		private static TreeNode splitedge(TreeNode w, TreeNode v, int q, int i, EnhancedSuffixArray esa) {			
			TreeNode wx = new TreeNode();
			
			wx.d           = w.d + q;
			wx.parent      = w;
			wx.parentLabel = esa.s.substring(esa.SUF[i]+w.d,esa.SUF[i]+w.d+q);
			
			v.parent = wx;
			v.parentLabel = esa.s.substring(esa.SUF[i-1]+w.d+q);
			
			return wx;
		}
	}
	
	private class Leaf extends TreeNode {
		public int j;
		
		public Leaf(int j) {
			this.j =j;
		}
	}
}
